#include "dfsalgorithm.h"
#include <stack>
#include <set>
#include <algorithm>
#include <climits>
#include <chrono>

DFSAlgorithm::DFSAlgorithm(int maxDepth)
    : SearchAlgorithm("深度优先搜索(IDA*)"), maxDepth(maxDepth)
{
}

SearchResult DFSAlgorithm::search(const PuzzleState& initial, const PuzzleState& goal)
{
    SearchResult result;
    result.algorithmName = algorithmName;
    result.success = false;
    result.steps = 0;
    result.nodesGenerated = 0;
    result.nodesExpanded = 0;
    result.timeElapsed = 0.0;
    
    auto startTime = std::chrono::high_resolution_clock::now();
    
    // 检查初始状态是否可解
    if (!initial.isSolvable(goal)) {
        auto endTime = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration<double, std::milli>(endTime - startTime);
        result.timeElapsed = duration.count();
        return result;
    }
    
    // 如果初始状态就是目标状态
    if (initial == goal) {
        result.success = true;
        result.steps = 0;
        result.solutionPath.push_back(initial);
        auto endTime = std::chrono::high_resolution_clock::now();
        auto duration = std::chrono::duration<double, std::milli>(endTime - startTime);
        result.timeElapsed = duration.count();
        return result;
    }
    
    // IDA*算法：dfs迭代加深 + A*启发式剪枝
    int nodesGenerated = 0;
    int nodesExpanded = 0;
    std::shared_ptr<SearchNode> solutionNode = nullptr;
    
    // 初始f值阈值为初始状态的启发式值
    int threshold = initial.manhattanDistance(goal);
    const int timeLimit = 15000; // 15秒时间限制
    
    while (threshold <= maxDepth && !solutionNode) {
        // 检查时间限制
        auto currentTime = std::chrono::high_resolution_clock::now();
        auto elapsed = std::chrono::duration<double, std::milli>(currentTime - startTime);
        if (elapsed.count() > timeLimit) {
            break;
        }
        
        int nextThreshold = INT_MAX;
        
        // 使用递归DFS进行深度限制搜索
        auto result_pair = idaStarSearch(initial, goal, 0, threshold, nullptr, -1, 
                                       nodesGenerated, nodesExpanded, nextThreshold, startTime, timeLimit);
        
        solutionNode = result_pair.first;
        if (solutionNode) {
            break;
        }
        
        // 如果没有找到解，增加阈值
        if (nextThreshold == INT_MAX) {
            break; // 没有更深的路径可以探索
        }
        threshold = nextThreshold;
    }
    
    auto endTime = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration<double, std::milli>(endTime - startTime);
    
    // 构建结果
    if (solutionNode != nullptr) {
        result.solutionPath = solutionNode->getPath();
        result.actionPath = solutionNode->getActionPath();
        int solutionSteps = result.solutionPath.size() - 1;
        
        // 放宽成功条件：只要找到解就算成功，不限制步数
        // 对于8数码，理论最大步数约为31步，对于15数码约为80步
        int maxReasonableSteps = (initial.getSize() == 3) ? 50 : 100;
        
        if (solutionSteps <= maxReasonableSteps) {
            result.success = true;
            result.steps = solutionSteps;
            
            // IDA*搜索是从初始状态向目标状态构建路径的，不需要反转
            // 路径已经是正确的顺序：从初始状态到目标状态
            
            // 确保path字段也被正确设置（用于演示功能）
            result.path = result.solutionPath;
        } else {
            // 找到解但步数过多，可能不是好解
            result.success = false;
            result.steps = 0;
            result.solutionPath.clear();
            result.actionPath.clear();
        }
    } else {
        // 没有找到解时，确保steps为0
        result.success = false;
        result.steps = 0;
        result.solutionPath.clear();
        result.actionPath.clear();
    }
    
    result.algorithmName = algorithmName;
    result.nodesGenerated = nodesGenerated;
    result.nodesExpanded = nodesExpanded;
    result.timeElapsed = duration.count();
    
    return result;
}

// IDA*算法的递归搜索实现
std::pair<std::shared_ptr<SearchNode>, bool> DFSAlgorithm::idaStarSearch(
    const PuzzleState& current, 
    const PuzzleState& goal,
    int g,  // 当前路径代价
    int threshold,  // f值阈值
    std::shared_ptr<SearchNode> parent,
    int action,
    int& nodesGenerated,
    int& nodesExpanded,
    int& nextThreshold,
    std::chrono::high_resolution_clock::time_point startTime,
    int timeLimit)
{
    // 检查时间限制
    auto currentTime = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration<double, std::milli>(currentTime - startTime);
    if (elapsed.count() > timeLimit) {
        return std::make_pair(nullptr, false);
    }
    
    // 创建当前节点
    auto currentNode = std::make_shared<SearchNode>(current, parent, action, g);
    nodesGenerated++;
    
    // 计算启发式值和f值
    int h = current.manhattanDistance(goal);
    int f = g + h;
    
    // 如果f值超过阈值，进行剪枝
    if (f > threshold) {
        nextThreshold = std::min(nextThreshold, f);
        return std::make_pair(nullptr, false);
    }
    
    // 检查是否达到目标状态
    if (current == goal) {
        return std::make_pair(currentNode, true);
    }
    
    nodesExpanded++;
    
    // 获取后继状态
    std::vector<PuzzleState> successors = current.getSuccessors();
    
    // 使用启发式排序：优先选择曼哈顿距离较小的状态
    std::sort(successors.begin(), successors.end(), 
             [&goal](const PuzzleState& a, const PuzzleState& b) {
                 return a.manhattanDistance(goal) < b.manhattanDistance(goal);
             });
    
    // 递归搜索每个后继状态
    for (const PuzzleState& successor : successors) {
        // 避免回到父状态
        if (parent && successor == parent->getState()) {
            continue;
        }
        
        // 确定动作类型
        int nextAction = -1;
        QPoint blankPos = current.getBlankPosition();
        QPoint newBlankPos = successor.getBlankPosition();
        
        if (newBlankPos.y() < blankPos.y()) nextAction = 0; // 上
        else if (newBlankPos.y() > blankPos.y()) nextAction = 1; // 下
        else if (newBlankPos.x() < blankPos.x()) nextAction = 2; // 左
        else if (newBlankPos.x() > blankPos.x()) nextAction = 3; // 右
        
        // 递归搜索
        auto result = idaStarSearch(successor, goal, g + 1, threshold, currentNode, nextAction,
                                  nodesGenerated, nodesExpanded, nextThreshold, startTime, timeLimit);
        
        if (result.second) { // 找到解
            return result;
        }
    }
    
    return std::make_pair(nullptr, false);
}